package 树;
/*
* 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

示例 1：

输入：arr = [0,1,2,3,4,5,6,7,8]
输出：[0,1,2,4,8,3,5,6,7]
解释：[0] 是唯一一个有 0 个 1 的数。
[1,2,4,8] 都有 1 个 1 。
[3,5,6] 有 2 个 1 。
[7] 有 3 个 1 。
按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]

*
* 这题没啥意思 但是可以提供一个方法Integer.bitCount
* 这个方法可以返回该数变成二进制中1的个数 算法思想是
* public static int bitCount(int i) {

    // HD, Figure 5-2

    i = i - ((i >>> 1) & 0x55555555);

    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

    i = (i + (i >>> 4)) & 0x0f0f0f0f;

    i = i + (i >>> 8);

    i = i + (i >>> 16);

    return i & 0x3f;

}
每两位bit为一组，分别统计有几个1，然后把结果存到这两个bit位上，如：11有2个1，结果为10，10替代11的存储到原位置。然后进行加法计算，把所有的结果加起来。加的过程中呢又可以两两相加，减少计算流程。

两个bit计算1的数量：0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b01 + 0b00 = 0b01 = 1，这样就清楚了。

算法实现如下：

首先整数i抹除左一位：i & 0x55555555，然后错位相加。(i >>> 1) & 0x55555555表示：左位移到右边，再把左位抹除，这样就可以计算两个bit位上1的个数了：0b1011=>0b0001 + 0b0101 = 0b0110左两位有1个1，右两位有2个1。

这时i中存储了每两位的统计结果，可以进行两两相加，最后求和。


* */
public class 二进制下1的个数 {
}
